/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年08月09日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
#include <string>
#include <math.h>
using namespace std;

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int sizeA = A.size();
        int sizeB = B.size();
        if(sizeA == 0 || sizeB == 0){
            return 0;
        }

        vector<vector<int>> dp(sizeA+1, vector<int>(sizeB+1, 0));
        int maxres = 0;
        for(int i = 1; i <= sizeA; i++){
            for(int j = 1; j <= sizeB; j++){
                if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    maxres = max(dp[i][j], maxres);
                }
            }
        }

        return maxres;
    }
};

int main(){
    string A = "GHGHJFGFGFYTFGHFGFGK";
    string B = "FGFHHGHGHFDGFHG";
    Solution C;
    cout << C.longestCommonSubstring(A, B)<<endl;
    return 0;
}